package cn.edu.zufe.mjt.bfs;

import java.util.*;

/**
 * 广度优先搜索——迷宫最短路径问题
 * 题目描述:
 * 给定一个大小为 m * n 的二维矩阵，其中每个元素表示一个格子。
 * 短阵中的每个格子可以是空白(用'0'表示)，或者是墙(用''表示)。
 * 你需要找到从给定的起始点到目标点之间的最短路径长度。
 * 你可以从当前格子向上下左右四个方向移动，且只能移动到相邻的空白格子。若无法到达目标点，请返回 -1。
 * 输入
 * 第一行输入两个整数 m 和 n(1 ≤ m,n ≤ 100)，表示矩阵的行数和列数.
 * "接下来输入一个 m xn 的矩阵，其中每个元素为'0'或'1'，表示空白格子或墙壁。
 * "接下来输入两个整数 x1和 y1(0 ≤ 1 ≤ m，0 ≤ y ≤ n)，表示起点坐标。
 * "接下来输入两个整数 x2 和 y2(0 ≤ x2 ≤ m,0 ≤ y2 ≤ n)，表示目标点坐标。
 * 输出
 * 输出一个整数，表示从起点到目标点的最短路径长度。如果目标点不可达，输出-1。
 */
public class ShortestPathMaze {
    public static void main(String[] args) {
        int[][] map = {
                {0, 1, 1, 0},
                {0, 0, 0, 1},
                {0, 0, 1, 0},
                {0, 0, 0, 0}};
        int x1 = 0;
        int y1 = 0;
        int x2 = 2;
        int y2 = 3;
        bfs(map, x1, y1, x2, y2);
    }

    /**
     * bfs 可以解决等权图的最短路径问题，什么是等权图，就是图中任意两点之间的距离都是相同的。
     * 且 bfs 是逐层访问的距离近的就会优先访问
     */
    private static void bfs(int[][] map, int x1, int y1, int x2, int y2) {
        int[][] visited = new int[map.length][map[0].length];
        for (int i = 0; i < map.length; i++) {
            Arrays.fill(visited[i], -1);
        }
        visited[x1][y1] = 0;
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{x1, y1});
        Map<String, String> parent = new HashMap<>();
        parent.put(x1 + "," + y1, null);
        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int x = current[0];
            int y = current[1];
            if (x == x2 && y == y2) {
                System.out.println(visited[x2][y2]);
                List<String> path = new LinkedList<>();
                for (String p = (x2 + "," + y2); p != null; p = parent.get(p))
                    path.add(0, p);
                System.out.println(path);
                return;
            }
            for (int i = 0; i < 4; i++) {
                int newX = x + dx[i];
                int newY = y + dy[i];
                if (newX >= 0 && newX < map.length && newY >= 0 && newY < map[0].length && map[newX][newY] == 0 && visited[newX][newY] == -1) {
                    visited[newX][newY] = visited[x][y] + 1;
                    queue.add(new int[]{newX, newY});
                    parent.put(newX + "," + newY, x + "," + y);
                }
            }
        }
        System.out.println(-1);
    }


    private static final int[] dx = {0, 0, -1, 1};
    private static final int[] dy = {-1, 1, 0, 0};
}
